//call this before using lca(u,v)

vi adj[nmax];
int timedfs=0;
int logn=int(log(nmax)/log(2)+1);
int fa[nmax][18], tin[nmax], tout[nmax];

void initdfs(int u, int pa=0) {
    tin[u]=++timedfs;
    fa[u][0]=pa;
    fori(i,1,logn) fa[u][i]=fa[fa[u][i-1]][i-1];
    fora(i,adj[u]) {
        int v=adj[u][i];
        if (v!=pa) initdfs(v, u); //dfs(v,u);
    }
    tout[u]=++timedfs;
}
//call this before using lca(u,v)
void init()
{
    initdfs(1);
    tin[0] = -1;
    tout[0] = 1111111111;
}
bool upper (int u, int v) {
	return (tin[u]<=tin[v] && tout[u]>=tout[v]);
}

int lca (int u, int v) {
	if (upper(u,v)) return u;
	if (upper(v,u)) return v;
	ford(i,logn,0) while (!upper(fa[u][i],v)) u=fa[u][i];
	return fa[u][0];
}


//lca using heavy light decomposition
vi adj[nmax];
int numcon[nmax], maxcon[nmax], tbef[nmax], troot[nmax], tin[nmax];
int timedfs=0;
void initdfs1(int u = 1, int pa=0) {
    maxcon[u]=-1; numcon[u]=0; troot[u]=u;
    fora(i,adj[u]) {
        int v=adj[u][i];
        if (v!=pa) {
            initdfs1(v,u);
            numcon[u]+=numcon[v];
            if (maxcon[u]==-1 || numcon[maxcon[u]]<numcon[v]) maxcon[u]=v;
        }
    }
}

void initdfs2(int u = 1, int pa=0) {
    tin[u]=++timedfs;
    if (maxcon[u]!=-1) {
        int v=maxcon[u];
        troot[v]=troot[u];
        initdfs2(v,u);
    }
    fora(i,adj[u]) {
        int v=adj[u][i];
        if (v!=pa && v!=maxcon[u]) {
            initdfs2(v,u);
            tbef[v]=u;
        }
    }
}

int lca(int u, int v) {
    while (troot[u]!=troot[v])
        if (tin[u]<tin[v]) v=tbef[troot[v]]; else u=tbef[troot[u]];
    return (tin[u]<tin[v]?u:v);
}

//Hopcroft Karp
vi adj[nmax];
int DX[nmax], DY[nmax], mx[nmax], my[nmax];
int N1, N2, n; //number of X, number of Y, max(N1, N2)
bool bfs() {
     // N = max(number of ver1, number of ver2)

    queue<int> q;
    fori(i,1,n) {
        if (mx[i]==0) q.push(i);
        DX[i]=DY[i]=0;
    }
    bool yet=false;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        fora(i,adj[u]) {
            int v=adj[u][i];
            if (DY[v]==0) {
                DY[v]=DX[u]+1;
                if (my[v]==0) yet=true; else {
                    DX[my[v]]=DY[v]+1;
                    q.push(my[v]);
                }
            }
        }
    }
    return yet;
}

bool dfs(int u) {
    fora(i,adj[u]) {
        int v=adj[u][i];
        if (DY[v]==DX[u]+1) {
            DY[v]=0;
            if (my[v]==0 || dfs(my[v])) {
                mx[u]=v;
                my[v]=u;
                return true;
            }
        }
    }
    return false;
}

int hopcroftkarp() {
    n = max(N1, N2);
    clear0(mx); clear0(my);
    int ans=0;
    while (bfs())
        fori(i,1,n)
            if (mx[i]==0 && dfs(i)) ++ans;
    return ans;
}


//dinitz
vi adj[nmax];
int d[nmax], flow[nmax][nmax], capacity[nmax][nmax];
int s1, s2, n;
bool bfs () {
    fori(i,1,n) d[i]=-1;
    queue<int> q; q.push(s1); d[s1]=0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        fora(i,adj[u]) {
            int v=adj[u][i];
            if (flow[u][v]<capacity[u][v] && d[v]==-1) {
                d[v]=d[u]+1;
                q.push(v);
            }
        }
    }
    return (d[s2]!=-1);
}

int dfs(int u, int tmpdelt) {
    if (u==s2) return tmpdelt;
    int du=d[u]; d[u]=0;
    fora(i,adj[u]) {
        int v=adj[u][i];
        if (d[v]==du+1 && flow[u][v]<capacity[u][v]) {
            int delta=dfs(v,min(tmpdelt,capacity[u][v]-flow[u][v]));
            if (delta) {
                flow[u][v]+=delta;
                flow[v][u]-=delta;
                return delta;
            }
        }
    }
    return 0;
}

int dinitz() {
    int ans=0;
    while (bfs()) {
        int delta;
        while (delta=dfs(s1,maxc)) ans+=delta;
    }
    return ans;
}

//Kuhn munkres
// n=number of X, m= number of Y
int fx[n], fy[m];
int kuhnmunkres(vi &mx) {
    vi mindel(m+1,maxc);
    vi my(m+1,0), cycle(m+1);
    bool free[m+1];

    fori(k,1,n){
        my[0]=k;
        fori(i,0,m) free[i]=true, mindel[i]=maxc;
        int i=0,j;
        do {
            free[i]=false;
            int ii=my[i], delta=maxc;
            fori(jj,1,m) if (free[jj]) {
                 int tmp:=c[ii,jj]-fx[ii]-fy[jj];
                 if (tmp<mindel[jj]) mindel[jj]=tmp, cycle[jj]=i;
                 if (mindel[jj]<delta) delta=mindel[jj], j=jj;
            }
            fori(jj,0,m) if (!free[jj]) {
                 fx[my[jj]]+=delta;
                 fy[jj]-=delta;
            }
            else mindel[jj]-=delta;
            i=j;
        } while (my[i]);
        do {
            j=cycle[i];
            my[i]=my[j];
            i=j;
        } while (i);
    }
    fori(i,1,m) mx[my[i]]=i;
    return -fy[0];
}

int s1, s2, n;
int p[nmax], trace[nmax], cost[nmax][nmax], flow[nmax][nmax], capacity[nmax][nmax];
bool dijkstraflow() {
    vi d(n+1,maxc), freedij(n+1,1);
    d[s1]=0;
    for (;;) {
        int u=0, minval=maxc;
        fori(v,1,n) if (d[v]<minval && freedij[v]) minval=d[u=v];
        if (!u) break;
        freedij[u]=0;
        fori(v,1,n) if (cost[u][v]>=0 && freedij[v] && flow[u][v]<capacity[u][v])
            if (flow[u][v]<0 && d[v]>d[u]+p[u]-p[v]-cost[u][v])
            {
                d[v]=d[u]+p[u]-p[v]-cost[u][v];
                trace[v]=u;
            }
            else if (flow[u][v]>=0 && d[v]>d[u]+p[u]-p[v]+cost[u][v])
            {
                d[v]=d[u]+p[u]-p[v]+cost[u][v];
                trace[v]=u;
            }
    }
    fori(u,1,n) if (p[u]<maxc) p[u]+=d[u];
    return !freedij[s2];
}

int mincostmaxflow() {
    clear0(p);
    while (dijkstraflow()) {
        int delta=maxc+1, v=s2;
        for (;v!=s1;) {
            int u=trace[v];
            if (flow[u][v]>=0) delta=min(delta,capacity[u][v]-flow[u][v]);
            else delta=min(delta,-flow[u][v]);
            v=u;
        }
        v=s2;
        for (;v!=s1;) {
            int u=trace[v];
            flow[u][v]+=delta;
            flow[v][u]-=delta;
            v=u;
        }
    }
    int ans=0;
    fori(u,1,n) fori(v,1,n)
      if (flow[u][v]>0) ans+=flow[u][v]*cost[u][v];
    return ans;
}
